1. Field of the Invention
This invention relates to the field of protocol analyzing systems, and more particularly to a frame relay protocol analyzing system having an improved pattern matching feature used to match anchored patterns in a protocol to enabled event triggers, filters, and/or statistical patterns in a protocol analyzer. The improved pattern matching feature exploits the relationships among the patterns being tested to facilitate automatic generation of an executable pattern matching program in real time. The executable code in the resulting pattern matching program is designed to optimize pattern matching efficiency by minimizing the number of comparisons required to identify which patterns match the input data.
2. Description of the Related Art
Pattern matching is an analysis technique commonly supported by existing protocol analyzing systems. The pattern matching technique is used to examine the data portion of individual frames that pass along a communication link between a first device and a second device. For anchored pattern matching, examining a frame means that a fixed portion of the frame is compared to a pattern to determine if that portion of the frame matches the pattern. For non-anchored pattern matching, examining a frame means that a variable portion of a frame is compared to a pattern to determine if that portion of the frame matches the pattern.
Depending on the result of a given comparison, the protocol analyzer may or may not initiate a predetermined event. For example, if a match exists between a frame and a given pattern then a predetermined event may occur. Alternatively, if a match does not exist between a frame and a given pattern then a predetermined event may not occur. Reasons for pattern matching include, but are not limited to, triggering events, capturing frames, filtering specific frames or types of frames, and identifying frame errors or statistical patterns within a series of frames.
One problem with pattern matching techniques in existing protocol analyzing systems is that they are performance inefficient. The inefficiencies are often the result of problems in the pattern matching comparison logic can that include, but are not limited to, the number of comparisons that are required between a frame and a single pattern, and the number of times a worst case comparison scenario occurs. Existing protocol analyzing systems use a brute force word-by-word comparison of a pattern against input data from a frame where the comparison process is repeated for each of a plurality of patterns that are enabled at pattern matching run time. In other words, the number of comparisons always equals the number of enabled patterns times the number of words in a pattern. This means that a word-by-word comparison will proceed even if, for example, the number of words in a pattern is greater than the number of words in the data portion of a frame so that no match could possibly occur. For a pattern matching scenario where there are 9 patterns to compare against a single frame of input data at 16 words per pattern, then 9*16=144 comparisons are required to complete the pattern matching against a single frame.
The result of the existing brute force comparison technique is that the worst case number of comparisons occurs for each of a plurality of patterns against each frame of input data. Because the overall performance of the pattern matching comparisons are determined by how quickly the worst case scenario can be processed, a given protocol analyzer using the brute force comparison technique may only be useful for monitoring low-speed communication links because the processing is so slow. One of the only ways to increase existing brute force pattern matching performance so that higher-speed communications links can be monitored is to use a higher performance processing engine in the protocol analyzer. However, using a higher performance processor can significantly increase the overall cost of the protocol analyzer thereby eliminating the market opportunity for a low-cost protocol analyzing equipment. In addition, although certain performance increases might be realized by developing alternative pattern matching comparison strategies for use with different sets of patterns, the alternative pattern matching comparison logic often requires custom pattern matching code from one set of patterns to the next and it is a problem when operator intervention is required to generate this custom code for each new set of patterns being used for each pattern matching session.
For these reasons there exists a long felt need for an improved pattern matching technique for use in a low-cost high-performance protocol analyzing system that addresses at least two problems: 1) the need for increased performance and/or efficiency of the pattern matching comparison logic for any given set of patterns; and 2) eliminating the need for operator intervention to assist in generating all or part of the program code used to execute the pattern matching comparison logic for any given set of patterns. A solution to these problems as disclosed and claimed herein has heretofore not been known.